4538. Вася и шары

Недавно Вася узнал, что с шарами можно играть в очень занимательную игру. В этой игре требуется выкладывать шары в виде различных геометрических фигур и тел. Сейчас Вася занимается укладкой шаров в форме равностороннего треугольника. Но вот незадача: иногда ему не хватает шаров, и тогда он хочет узнать, какой наибольшей длины сторону может иметь такой треугольник при имеющемся количестве шаров.

Помогите Васе: напишите программу, которая будет вычислять n – длину стороны равностороннего треугольника для заданного числа шаров k.

Ниже приведён пример укладки шаров в виде равностороннего треугольника:

Вход. Одно натуральное число k (0 ≤ k ≤ 2 *10⁸) – количество имеющихся шаров.

Выход. Выведите число n – ответ задачи.

Пример входа	Пример выхода
5	2

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Если n – длина стороны треугольника, то для полной его укладки требуется

1 + 2 + … + n = n * (n + 1) / 2

шаров.

Пусть в наличии имеется k шаров. Чтобы найти максимальное возможное n, решим уравнение

n * (n + 1) / 2 = k

и округлим неотрицательный корень вниз до ближайшего целого числа.

Решим квадратное уравнение:

n² + n – 2k = 0,

d = 1 + 8k, n =

Ответом будет значение .

Реализация алгоритма

Читаем входное значение k.

scanf("%d",&k);

Вычисляем и выводим ответ.

n = int((-1 + sqrt(1.0 + 8*k)) / 2.0);

printf("%d\n",n);

Реализация алгоритма – бинарный поиск

#include <stdio.h>

long long n, k, l, r, mid, res;

long long f(long long n)

{

return n * (n + 1) / 2;

}

int my_upper_bound(int start, int end, int x)

{

while (start < end)

{

int mid = (start + end) / 2;

if (f(mid) > x)

end = mid;

else

start = mid + 1;

}

return start;

}

int main()

{

scanf("%lld", &k);

// find min n: f(n) >= k

if (k == 0) res = 0;

else if (k == 1) res = 1;

else res = my_upper_bound(0, k, k) - 1;

printf("%d\n", res);

}

Реализация алгоритма – O(sqrt(n))

#include <stdio.h>

long long n, k, res;

long long f(long long n)

{

return n * (n + 1) / 2;

}

int main()

{

scanf("%lld", &k);

// find min n: f(n) >= k

n = 0;

while (f(n) <= k) n++;

printf("%d\n", n);

}